package com.zhzh.sc.demo.leetcode.learn.link;

/**
 * @version V1.0
 * @Copyright 2021- csdn - Powered By 长沙研发中心
 * @author: zhzh
 * @date: 2022/7/15 5:13 PM
 */
public class ClassicProblems {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * https://leetcode.com/explore/learn/card/linked-list/219/classic-problems/1205/
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

    /**
     * https://leetcode.com/explore/learn/card/linked-list/219/classic-problems/1207/
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1, head);
        ListNode tmp =  dummy;
        while (tmp != null) {
            if (tmp.next != null && tmp.next.val == val) {
                tmp.next = tmp.next.next;
            } else {
                tmp = tmp.next;
            }
        }

        return dummy.next;
    }

    /**
     * https://leetcode.com/explore/learn/card/linked-list/219/classic-problems/1208/
     * First, let the first node be the end of oddList, second node be the head and tail of evenList.
     * Main idea is that keep track the end of oddList and the head as well as tail of evenList. For each odd index node, put it to between end of oddList and head of evenList. Then update those three tracks.
     * @param head
     * @return
     */
    public ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode oddEnd = head, evenHead = head.next, evenEnd = evenHead;
        while(evenEnd !=null && evenEnd.next != null) {
            ListNode curOdd = evenEnd.next;
            ListNode curEven = curOdd.next;
            oddEnd.next = curOdd;
            curOdd.next = evenHead;
            evenEnd.next = curEven;
            oddEnd = curOdd;
            evenEnd = curEven;
        }
        return head;
    }

    /**
     * https://leetcode.com/explore/learn/card/linked-list/219/classic-problems/1209/
     * @param head
     * @return
     */
    public static boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        // Find the middle Node
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode mHead = null;
        // Reverse the list from mid to end
        while (slow != null) {
            ListNode node = new ListNode(slow.val);
            node.next = mHead;
            mHead = node;
            slow = slow.next;
        }
        // Check if values are matching or not
        while (mHead != null) {
            if (mHead.val != head.val) {
                return false;
            }
            head = head.next;
            mHead = mHead.next;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        System.out.println(isPalindrome(head));
    }

}
